package acm.上海理工大学同步赛;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 找出一种f赢的情况,抽到一个数，让剩下的无法互相消除的数种类是偶数个（并查集）。
 * 并查集个数如果是奇数个，则f赢，否则s赢
 */
public class K {
    public static void main(String[] args) {

    }
    public static void fun(long n){
        List<Long> list=new ArrayList<>();
        list.add(1L);
        for (long i = 2; i <= n; i++) {
            for (int j = 0; j < list.size(); j++) {
                if (i% list.get(j) ==0){
                    list.set(j,2L);
                    break;
                }
            }
        }
        System.out.println(list.size()%2==0?"s":"f");
    }
    static {
        List<Integer> list =Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
        System.out.println(f(list));
    }

    public static boolean f(List<Integer> list){
        if (list.size()==1){
            return true;
        }
        for (int i = 0; i < list.size(); i++) {
            List<Integer> copy = new ArrayList<>(list);
            Integer curr = copy.get(i);
            for (int j = 0;copy.get(j) <= curr&&copy.size()>0; j++) {
                if (curr%copy.get(j)==0){
                    copy.remove(j);
                    j--;
                }
            }
            if (s(copy)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 后手函数
     * @param list
     * @return
     */
    public static boolean s(List<Integer> list){
        if (list.size()==1){
            return false;
        }
        for (int i = 0; i < list.size(); i++) {
            List<Integer> copy = list.stream().collect(Collectors.toList());
            Integer curr = copy.get(i);
            for (int j = 0; copy.get(j) <= curr; j++) {
                if (curr%copy.get(j)==0){
                    copy.remove(j);
                    j--;
                }
            }
            if (f(copy)) {
                return false;
            }
        }
        return true;
    }
//    s2,
//    12345678,f1
//    1234567,f
//    123456,f
//    12345,f
//    1234,f
//    123,f
//    12,f
//    1,f
    public static boolean get(long index,long[] map){
        int i= (int) (index/map.length);
        int d= (int) (index%64);
        return (1L <<d & map[i])==0;    //0表示未使用
    }

    public static void set(long index,long[] map){
        int i= (int) (index/map.length);
        int d= (int) (index%64);
        map[i]=map[i] | 1L<<d;      //1表示使用
    }
}
